﻿//力扣：219. 存在重复元素 II
//链接：https://leetcode.cn/problems/contains-duplicate-ii/description/


//方法：哈希表
//时间复杂度：O(n)

//算法原理：
//解决该问题需要我们快速定位到两个信息：
//    • 两个相同的元素；
//    • 这两个相同元素的下标。
//因此，我们可以使⽤「哈希表」，令数组内的元素做 key 值，该元素所对应的下标做 val 值，将「数组元素」和「下标」绑定在⼀起，存⼊到「哈希表」中。
class Solution 
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;                   // 定义哈希表

        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(nums[i]))                    // 若当前元素在哈希表中出现过，则说明有重复元素
            {
                if (i - hash[nums[i]] <= k)             // 若当前元素与上次出现的元素距离小于等于k，则说明有重复元素
                {
                    return true;
                }
            }

            // 若当前元素没有出现过，则将其加入哈希表
            // （注意：这里可以进行覆盖，因为abs(i - j) <= k，选距离越近的元素，如果最近的两个元素下标差的绝对值都大于k，则说明其他的元素也不满足条件）
            hash[nums[i]] = i;
            
        }

        return false;
    }
};
//思考题：
//如果数组内存在⼤量的「重复元素」，⽽我们判断下标所对应的元素是否符合条件的时候，需要将不同下标的元素作⽐较，怎么处理这个情况呢？

//答：这⾥运⽤了⼀个「⼩贪⼼」。
//我们按照下标「从⼩到⼤」的顺序遍历数组，当遇到两个元素相同，并且⽐较它们的下标时，这两个下标⼀定是距离最近的，因为：
//• 如果当前判断符合条件直接返回 true ，⽆需继续往后查找。
//• 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配（因为下标在逐渐变⼤），那么我们可以⼤胆舍去前⼀个存储的下标，转⽽将其换成新的下标，继续匹配。